#
# @lc app=leetcode.cn id=844 lang=python3
#
# [844] 比较含退格的字符串
#

"""
本题有两种解法：栈或双指针
双指针法：
设置两个指针来分别遍历字符串 s 和 t （倒序遍历），
同时用 skipS 或 skipT 分别记录对应字符串中出现 '#' 的数量
此时在遍历字符串时会出现以下三种情况：
  1. 当前字符是 # ，skipS++ ，表示前方有一个字符要被执行的退格（可能存在多个连续 '#'的情况）
  2. 当前字符不是 '#' 且 skipS > 0 ，将 skipS-- ，表示当前字符是被执行退格的字符，不参与对比
  3. 当前字符不是 '#' 且 skipS = 0 ，跳出当前循环，表示当前字符无需执行退格，跳出循环来参与对比
跳出字符串遍历的循环后，在大循环内可以得到无需执行退格的两个字符的指针，比较这两个字符是否相同：
  1. 如果不相同返回 False ，表示这两个字符串不相同
  2. 相同返回 True ，表示这两个字符串相同
  3. 特殊情况，一个字符串已经遍历完，而另一个还未遍历完，则返回 False，遍历途中位置不一致，字符必然不相等
"""

# @lc code=start
class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        i, j = len(s) - 1, len(t) - 1
        skipS = skipT = 0

        while i >= 0 or j >= 0:
            while i >= 0:
                if s[i] == '#':
                    skipS += 1
                    i -= 1 
                elif skipS > 0:
                    skipS -= 1
                    i -= 1
                else:
                    break
            
            while j >= 0:
                if t[j] == '#':
                    skipT += 1
                    j -= 1
                elif skipT > 0:
                    skipT -= 1
                    j -= 1
                else:
                    break

            if i >= 0 and j >= 0:
                if s[i] != t[j]:
                    return False
            elif i>=0 or j>= 0:
                return False
            
            i -= 1
            j -= 1
            
        return True

# @lc code=end
